﻿#define _CRT_SECURE_NO_WARNINGS 1

/*
无解释，用栈插入可以轻松解决
*/

//每日一题_04
//BM44 有效括号序列
//https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2?tpId=295&tqId=726&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj

#include<iostream>
#include<stack>
using namespace std;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return bool布尔型
     */
    bool isValid(string s) {
        stack<char> stack_in;

        for (int i = 0; i < s.size(); i++) {
            //栈为空直接插入
            if (stack_in.empty()) {
                stack_in.push(s[i]);
            }
            else {
                //栈不为空，判断后插入
                //相同则删除
                if (stack_in.top() == '[' && s[i] == ']' ||
                    stack_in.top() == '(' && s[i] == ')' ||
                    stack_in.top() == '{' && s[i] == '}')
                {
                    stack_in.pop();
                }
                else {
                    //不同继续插入
                    stack_in.push(s[i]);
                }
            }
        }

        return stack_in.empty();
    }
};

int main()
{
    Solution s;
    cout << s.isValid("()") << endl;
    return 0;
}